package chapter02;

import java.util.ArrayList;
import java.util.List;

public class RotateRight61 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * 将链表中每个节点向右移动K个位置，也就是将链表中倒数第K个节点作为头节点，其前面的所有节点放在原链表尾节点之后。
     * 先将节点形成环 最后在新尾节点处断开
     * 将原链表节点从0~n-1标记  倒数第k个节点的标记为n-k%n
     * 两种办法
     * 1)找到新头节点
     *   从头节点开始 初始index=0 找到index==n-k%n时 此时头节点即为新头节点
     *   头节点移动 index++
     * 2)找新尾节点
     *  从尾节点开始 初始index=0 找到index==n-k%n时 此时尾节点即为新尾节点
     *  尾节点移动 index++
     */
    public ListNode rotateRight(ListNode head, int k){
        if(head==null||head.next==null){
            return head;
        }
        int length=0;
        ListNode headNode=head;
        ListNode tailNode=null;
        while (head!=null){
            length++;
            tailNode=head;
            head=head.next;
        }
        tailNode.next=headNode;
        int index=0,pos=length-k%length; //此处从0开始 找到尾
        while (index!=pos){
            tailNode=tailNode.next;
            index++;
        }
        headNode=tailNode.next;
        tailNode.next=null;
        return headNode;
    }

    //数组存放节点
    public ListNode rotateRight1(ListNode head, int k){
        if(head==null||head.next==null){
            return head;
        }
        List<ListNode> list=new ArrayList<>();
        while (head!=null){
            list.add(head);
            head=head.next;
        }
        int length=list.size();
        ListNode[] arrayNode=new ListNode[length];
        for(int i=0;i<length;i++){
            int index=(i+k)%length;
            arrayNode[index]=list.get(i);
        }
        ListNode headNode=new ListNode(-1);
        ListNode p=headNode;
        for(int i=0;i<length;i++){
            p.next=arrayNode[i];
            p=p.next;
        }
        p.next=null;
        return headNode.next;
    }
}
